home *** CD-ROM | disk | FTP | other *** search
/ Libris Britannia 4 / science library(b).zip / science library(b) / ELECTRON / 0989.ZIP / ESPRESSO.ARC / UCBQSORT.C < prev   
Text File  |  1987-03-13  |  8KB  |  201 lines
  1. /* @(#)qsort.c  4.2 (Berkeley) 3/9/83 */
  2.  
  3. /*
  4.  * qsort.c:
  5.  * Our own version of the system qsort routine which is faster by an average
  6.  * of 25%, with lows and highs of 10% and 50%.
  7.  * The THRESHold below is the insertion sort threshold, and has been adjusted
  8.  * for records of size 48 bytes.
  9.  * The MTHREShold is where we stop finding a better median.
  10.  */
  11.  
  12. #define         THRESH          4               /* threshold for insertion */
  13. #define         MTHRESH         6               /* threshold for median */
  14.  
  15. static  int             (*qcmp)();              /* the comparison routine */
  16. static  int             qsz;                    /* size of each record */
  17. static  int             thresh;                 /* THRESHold in chars */
  18. static  int             mthresh;                /* MTHRESHold in chars */
  19.  
  20. /*
  21.  * qsort:
  22.  * First, set up some global parameters for qst to share.  Then, quicksort
  23.  * with qst(), and then a cleanup insertion sort ourselves.  Sound simple?
  24.  * It's not...
  25.  */
  26. #undef min
  27. #undef max
  28. qsort(base, n, size, compar)
  29.         char    *base;
  30.         int     n;
  31.         int     size;
  32.         int     (*compar)();
  33. {
  34.         register char c, *i, *j, *lo, *hi;
  35.         char *min, *max;
  36.  
  37.         if (n <= 1)
  38.                 return;
  39.         qsz = size;
  40.         qcmp = compar;
  41.         thresh = qsz * THRESH;
  42.         mthresh = qsz * MTHRESH;
  43.         max = base + n * qsz;
  44.         if (n >= THRESH) {
  45.                 qst(base, max);
  46.                 hi = base + thresh;
  47.         } else {
  48.                 hi = max;
  49.         }
  50.         /*
  51.          * First put smallest element, which must be in the first THRESH, in
  52.          * the first position as a sentinel.  This is done just by searching
  53.          * the first THRESH elements (or the first n if n < THRESH), finding
  54.          * the min, and swapping it into the first position.
  55.          */
  56.         for (j = lo = base; (lo += qsz) < hi; )
  57.                 if ((*qcmp)(j, lo) > 0)
  58.                         j = lo;
  59.         if (j != base) {
  60.                 /* swap j into place */
  61.                 for (i = base, hi = base + qsz; i < hi; ) {
  62.                         c = *j;
  63.                         *j++ = *i;
  64.                         *i++ = c;
  65.                 }
  66.         }
  67.         /*
  68.          * With our sentinel in place, we now run the following hyper-fast
  69.          * insertion sort. For each remaining element, min, from [1] to [n-1],
  70.          * set hi to the index of the element AFTER which this one goes.
  71.          * Then, do the standard insertion sort shift on a character at a time
  72.          * basis for each element in the frob.
  73.          */
  74.         for (min = base; (hi = min += qsz) < max; ) {
  75.                 while ((*qcmp)(hi -= qsz, min) > 0)
  76.                         /* void */;
  77.                 if ((hi += qsz) != min) {
  78.                         for (lo = min + qsz; --lo >= min; ) {
  79.                                 c = *lo;
  80.                                 for (i = j = lo; (j -= qsz) >= hi; i = j)
  81.                                         *i = *j;
  82.                                 *i = c;
  83.                         }
  84.                 }
  85.         }
  86. }
  87.  
  88. /*
  89.  * qst:
  90.  * Do a quicksort
  91.  * First, find the median element, and put that one in the first place as the
  92.  * discriminator.  (This "median" is just the median of the first, last and
  93.  * middle elements).  (Using this median instead of the first element is a big
  94.  * win).  Then, the usual partitioning/swapping, followed by moving the
  95.  * discriminator into the right place.  Then, figure out the sizes of the two
  96.  * partions, do the smaller one recursively and the larger one via a repeat of
  97.  * this code.  Stopping when there are less than THRESH elements in a partition
  98.  * and cleaning up with an insertion sort (in our caller) is a huge win.
  99.  * All data swaps are done in-line, which is space-losing but time-saving.
  100.  * (And there are only three places where this is done).
  101.  */
  102.  
  103. static
  104. qst(base, max)
  105.         char *base, *max;
  106. {
  107.         register char c, *i, *j, *jj;
  108.         register int ii;
  109.         char *mid, *tmp;
  110.         int lo, hi;
  111.  
  112.         /*
  113.          * At the top here, lo is the number of characters of elements in the
  114.          * current partition.  (Which should be max - base).
  115.          * Find the median of the first, last, and middle element and make
  116.          * that the middle element.  Set j to largest of first and middle.
  117.          * If max is larger than that guy, then it's that guy, else compare
  118.          * max with loser of first and take larger.  Things are set up to
  119.          * prefer the middle, then the first in case of ties.
  120.          */
  121.         lo = max - base;                /* number of elements as chars */
  122.         do      {
  123.                 mid = i = base + qsz * ((lo / qsz) >> 1);
  124.                 if (lo >= mthresh) {
  125.                         j = ((*qcmp)((jj = base), i) > 0 ? jj : i);
  126.                         if ((*qcmp)(j, (tmp = max - qsz)) > 0) {
  127.                                 /* switch to first loser */
  128.                                 j = (j == jj ? i : jj);
  129.                                 if ((*qcmp)(j, tmp) < 0)
  130.                                         j = tmp;
  131.                         }
  132.                         if (j != i) {
  133.                                 ii = qsz;
  134.                                 do      {
  135.                                         c = *i;
  136.                                         *i++ = *j;
  137.                                         *j++ = c;
  138.                                 } while (--ii);
  139.                         }
  140.                 }
  141.                 /*
  142.                  * Semi-standard quicksort partitioning/swapping
  143.                  */
  144.                 for (i = base, j = max - qsz; ; ) {
  145.                         while (i < mid && (*qcmp)(i, mid) <= 0)
  146.                                 i += qsz;
  147.                         while (j > mid) {
  148.                                 if ((*qcmp)(mid, j) <= 0) {
  149.                                         j -= qsz;
  150.                                         continue;
  151.                                 }
  152.                                 tmp = i + qsz;  /* value of i after swap */
  153.                                 if (i == mid) {
  154.                                         /* j <-> mid, new mid is j */
  155.                                         mid = jj = j;
  156.                                 } else {
  157.                                         /* i <-> j */
  158.                                         jj = j;
  159.                                         j -= qsz;
  160.                                 }
  161.                                 goto swap;
  162.                         }
  163.                         if (i == mid) {
  164.                                 break;
  165.                         } else {
  166.                                 /* i <-> mid, new mid is i */
  167.                                 jj = mid;
  168.                                 tmp = mid = i;  /* value of i after swap */
  169.                                 j -= qsz;
  170.                         }
  171.                 swap:
  172.                         ii = qsz;
  173.                         do      {
  174.                                 c = *i;
  175.                                 *i++ = *jj;
  176.                                 *jj++ = c;
  177.                         } while (--ii);
  178.                         i = tmp;
  179.                 }
  180.                 /*
  181.                  * Look at sizes of the two partitions, do the smaller
  182.                  * one first by recursion, then do the larger one by
  183.                  * making sure lo is its size, base and max are update
  184.                  * correctly, and branching back.  But only repeat
  185.                  * (recursively or by branching) if the partition is
  186.                  * of at least size THRESH.
  187.                  */
  188.                 i = (j = mid) + qsz;
  189.                 if ((lo = j - base) <= (hi = max - i)) {
  190.                         if (lo >= thresh)
  191.                                 qst(base, j);
  192.                         base = i;
  193.                         lo = hi;
  194.                 } else {
  195.                         if (hi >= thresh)
  196.                                 qst(i, max);
  197.                         max = j;
  198.                 }
  199.         } while (lo >= thresh);
  200. }
  201.